#ifndef __Map_hpp__
#define __Map_hpp__

#include "Exception.hpp"

namespace ge {

//----------------------------------------------------------------------------//
// Map< K, V, C > 
//----------------------------------------------------------------------------//

template < class K, class V, class C = Less< K > >
class Map
{
 protected:

     //-----------------------------------------------------------------------//
     // Node
     //-----------------------------------------------------------------------//

     struct Node
     {
      friend class Map;
      friend class Iterator;
      friend class Proxy;

      private:

          Node( void ); // no source
          ~Node( void ); // no source
          Node( const Node& ); // no source
          Node& operator = ( const Node& ); // no source

          bool IsLeftChild( void ) const
          {
               return m_parent && m_parent -> m_left_child == this;
          }

          bool IsRightChild( void ) const
          {
               return m_parent && m_parent -> m_right_child == this;
          }

          void SetLeftChild( Node* _n )
          {
               if( (m_left_child = _n) ) _n -> m_parent = this;
          }

          void SetRightChild( Node* _n )
          {
               if( (m_right_child = _n) ) _n -> m_parent = this;
          }

          Node* m_left_child;
          Node* m_right_child;
          Node* m_parent;
          K m_key;
          V m_value;
          bool m_red_color;
     };

 public:

     //-----------------------------------------------------------------------//
     // Iterator
     //-----------------------------------------------------------------------//

     class Iterator
     {
      friend class Map;

      public:

          Iterator( void ) : m_node( 0 )
          {
          }

          Iterator( const Iterator& _iter ) : m_node( _iter.m_node )
          {
          }

          Iterator& operator = ( const Iterator& _iter ) 
          { 
               m_node = _iter.m_node;

               return *this;
          }

          bool IsValid( void ) const
          {
               return m_node != 0;
          }

          bool ToNext( void ) const
          {
                if( !m_node ) return false;
                if( m_node -> m_right_child ) m_node = _Min( m_node -> m_right_child );
                else if( m_node -> IsLeftChild() ) m_node = m_node -> m_parent;
                else
                {
                     while( m_node -> IsRightChild() ) m_node = m_node -> m_parent;
                     m_node = m_node -> m_parent;
                }

                return m_node != 0;
          }

          bool ToPrev( void ) const
          {
                if( !m_node ) return false;
                if( m_node -> m_left_child ) m_node = _Max( m_node -> m_left_child );
                else if( m_node -> IsRightChild() ) m_node = m_node -> m_parent;
                else
                {
                     while( m_node -> IsLeftChild() ) m_node = m_node -> m_parent;
                     m_node = m_node -> m_parent;
                }

                return m_node != 0;
          }

          Iterator& operator ++ ( void ) const
          { 
               ToNext();
               return const_cast< Iterator& >( *this );
          }

          Iterator& operator -- ( void ) const
          { 
               ToPrev();
               return const_cast< Iterator& >( *this );
          }

          Iterator operator ++ ( int ) const
          { 
               Iterator _ret( *this );
               ToNext();
               return _ret;
          }

          Iterator operator -- ( int ) const
          { 
               Iterator _ret( *this );
               ToPrev();
               return _ret;
          }

		        operator bool ( void ) const
          {
               return IsValid(); 
          }

          const K& Key( void ) const
          {
               geDebugAssertT( FailedAccess, IsValid(), "Map< K, V, C >::Iterator - No key" );
               return m_node -> m_key;
          }

          V& Value( void ) const
          {
               geDebugAssertT( FailedAccess, IsValid(), "Map< K, V, C >::Iterator - No value" );
               return const_cast< V& >( m_node -> m_value ); 
          }

		        V& operator * ( void ) const
          { 
               geDebugAssertT( FailedAccess, IsValid(), "Map< K, V, C >::Iterator - No value" );
               return const_cast< V& >( m_node -> m_value ); 
          }

		        V* operator -> ( void ) const
          { 
               geDebugAssertT( FailedAccess, IsValid(), "Map< K, V, C >::Iterator - No value" );
               return &const_cast< V& >( m_node -> m_value ); 
          }

          Iterator Root( void ) const
          {
               return Iterator( _Root( m_node ) );    
          }

          Iterator First( void ) const
          {
               return Iterator( _Min( _Root( m_node ) ) );    
          }

          Iterator Last( void ) const
          {
               return Iterator( _Max( _Root( m_node ) ) );    
          }

          Iterator Next( void ) const
          {
               return ++ Iterator( *this );
          }

          Iterator Prev( void ) const
          {
               return ++ Iterator( *this );
          }

          bool operator == ( const Iterator& _iter ) const
          {
               return m_node == _iter.m_node;
          }

          bool operator != ( const Iterator& _iter ) const
          {
               return m_node != _iter.m_node;
          }

      protected:

          Iterator( const Node* _node ) : m_node( const_cast< Node* >( _node ) )
          {
          }

          static Node* _Min( Node* _node )
          {
               while( _node && _node -> m_left_child ) _node = _node -> m_left_child;
               return _node;
          }

          static Node* _Max( Node* _node )
          {
               while( _node && _node -> m_right_child ) _node = _node -> m_right_child;
               return _node;
          }

          static Node* _Root( Node* _node )
          {
               while( _node && _node -> m_parent ) _node = _node -> m_parent;
               return _node;
          }

          mutable Node* m_root;
          mutable Node* m_node;
     };

     //-----------------------------------------------------------------------//
     // Proxy
     //-----------------------------------------------------------------------//

     class Proxy
     {
      friend class Map;

      public:

          Proxy( const Proxy& _proxy ) : m_map( _proxy.m_map ), m_key( _proxy.m_key )
          {
          }

          Proxy& operator = ( const Proxy& _proxy )
          {
               m_map = _proxy.m_map;
               m_key = _proxy.m_key;

               return *this;
          }

          const K& Key( void ) const
          {
               return m_key;
          }

          V& Value( void )
          {
               Node* _node = m_map._Search( m_key );
               if( !_node ) _node = m_map._Insert( m_key, V() );
               assert( _node );
               return _node -> m_value;
          }

          V& operator = ( const V& _value ) 
          {
               Node* _node = m_map._Search( m_key );

               if( !_node )
               {
                    _node = m_map._Insert( m_key, _value );
                    assert( _node );
                    return _node -> m_value;
               }
               
               return (_node -> m_value = _value );
          }

          operator V& ( void )
          {
               return Value();
          }

          Map< K, V, C >& Map( void )
          {
               return m_map;
          }

          bool IsInMap( void ) const
          {
               return m_map._Search( m_key ) != 0;
          }

      private:

          Proxy( Map& _map, const K& _key ) : m_map( _map ), m_key( _key )
          {
          }

          Proxy( void ); // no source

          Map& m_map;
          const K& m_key;
     };


     //-----------------------------------------------------------------------//
     // Map
     //-----------------------------------------------------------------------//

     Map( void ) : m_root( 0 ), m_count( 0 )
     {
     }

     Map( const Map& _map ) : m_root( 0 ), m_count( _map.m_count )
     {
          _CopyNode( m_root, _map.m_root );
     }

     Map& operator = ( const Map& _map )
     {
          if( m_root != _map.m_root )
          {
               _DeleteTree( m_root ); 
               _CopyNode( m_root, _map.m_root );
               m_count = _map.m_count;
          }

          return *this;
     }

     Proxy operator [] ( const K& _key )
     {
          return Proxy( *this, _key );
     }

     void Clear( void )
     {
          if( m_root )
          {
               _DeleteTree( m_root );
               m_root = 0;
               m_count = 0;
          }
     }

     Iterator First( void ) const
     {
          return Iterator( Iterator::_Min( const_cast< Node* >( m_root ) ) );
     }

     Iterator Last( void ) const
     {
          return Iterator( Iterator::_Max( const_cast< Node* >( m_root ) ) );
     }

     Iterator Root( void ) const
     {
          return Iterator( m_root );
     }

     Iterator Search( const K& _key ) const
     {
          return Iterator( _Search( _key ) );
     }

     void Remove( const K& _key )
     {
          Node* _node = _Search( _key );
          if( _node ) _Remove( _node );
     }

     Iterator Remove( const Iterator& _iter )
     {
          Iterator _next = _iter.Next();
          if( !_next ) _next = _iter.Prev();
          if( _iter ) _Remove( _iter.m_node );
          return _next;
     }

     Iterator Rename( const Iterator& _iter, const K& _new_key )
     {
          return Iteator( _Rename( _iter.m_node, _new_key ) ); 
     }

     Iterator Rename( const K& _key, const K& _new_key )
     {
          return Iterator( _Rename( _Search( _key ), _new_key ) ); 
     }

     Iterator InsertIfNotExists( const K& _key, const V& _value )
     {
          Node* _node = _Search( _key );
          if( _node ) return _node -> m_value;
          Iterator( _Insert( _key, _value ) );
     }

     V& Insert( const K& _key, const V& _value )
     {
          Node* _node = _Search( _key );
          if( !_new ) _node = _Insert( _key, _value );
          return Iterator( _node );
     }

     Proxy GetProxy( const K& _key )
     {
          return Proxy( *this, _key );
     }

     uint Count( void ) const
     {
          return m_count;
     }

     uint Size( void ) const
     {
          return m_count;
     }

     bool IsEmpty( void ) const
     {
          return m_count == 0;
     }

     bool NonEmpty( void ) const
     {
          return m_count != 0;
     }

     void Swap( Map& _map )
     {
          ge::Swap( m_root, _map.m_root );
          ge::Swap( m_count, _map.m_count );
     }

 protected:

     Node* _Search( const K& _key ) const
     {
          for( Node* i = m_root; i; )
          {
               if( ms_cmp.Eq( _key, i -> m_key ) ) return i;
               else if( ms_cmp.Lt( _key, i -> m_key ) ) i = i -> m_left_child;
               else i = i -> m_right_child;
          }

          return 0;
     }

     void _SetRoot( Node* _root )
     {
          if( (m_root = _root) )
          {
               m_root -> m_red_color = false;
               m_root -> m_parent = 0;
          }
     }

     bool _Insert1( Node* _node )
     {
          // return false if node with equal key of already exists

          if( !m_root )
          {
               _SetRoot( _node );
               m_count = 1;

               return true;
          }

          const K& _key = _node -> m_key;

          for( Node* i = m_root; i; )
          {
               const K& _ckey = i -> m_key;

               if( ms_cmp.Eq( _key, _ckey ) ) return false;
               else if( ms_cmp.Lt( _key, _ckey ) )
               {
                    if( i -> m_left_child ) i = i -> m_left_child;
                    else
                    {
                         i -> SetLeftChild( _node );
                         ++ m_count;
                         return true;
                    }
               }
               else
               {
                    if( i -> m_right_child ) i = i -> m_right_child;
                    else
                    {
                         i -> SetRightChild( _node );
                         ++ m_count;
                         return true;
                    }
               }
          }

          return false;
     }

     void _Insert2( Node* _node )
     {
          for( Node *_parent, *_parent2, *_uncle; _node -> m_parent && _node -> m_parent -> m_red_color; )
          {
               _parent = _node -> m_parent;
               _parent2 = _parent -> m_parent;

               if( _parent -> IsLeftChild() )
               {
                    _uncle = _parent2 -> m_right_child;

                    if( _uncle && _uncle -> m_red_color )
                    {
                         _parent -> m_red_color = false;
                         _uncle -> m_red_color = false;
                         _parent2 -> m_red_color = true;
                         _node = _parent2;
                    }
                    else
                    {
                         if( _node -> IsRightChild() )
                         {
                              _node = _parent;
                              _RotateLeft( _node );
                              _parent = _node -> m_parent;
                              _parent2 = _parent -> m_parent;
                         }

                         _parent -> m_red_color = false;
                         _parent2 -> m_red_color = true;
                         _RotateRight( _parent2 );
                    }
               }
               else
               {
                    _uncle = _parent2 -> m_left_child;

                    if( _uncle && _uncle -> m_red_color )
                    {
                         _parent -> m_red_color = false;
                         _uncle -> m_red_color = false;
                         _parent2 -> m_red_color = true;
                         _node = _parent2;
                    }
                    else
                    {
                         if( _node -> IsLeftChild() )
                         {
                              _node = _parent;
                              _RotateRight( _node );
                              _parent = _node -> m_parent;
                              _parent2 = _parent -> m_parent;
                         }

                         _parent -> m_red_color = false;
                         _parent2 -> m_red_color = true;
                         _RotateLeft( _parent2 );
                    }
               }
          }

          m_root -> m_red_color = false;
     }

     Node* _Insert( const K& _key, const V& _value )
     {
          Node* _node = _New( _key, _value );
          bool _inserted = _Insert1( _node );
          assert( _inserted && "node with equal key of already exists" );

          _Insert2( _node );

          return _node;
     }

     void _RotateLeft( Node* _node )
     {
          assert( _node );

          Node* _right = _node -> m_right_child;
          _node -> SetRightChild( _right -> m_left_child );
          if( _node -> IsLeftChild() ) _node -> m_parent -> SetLeftChild( _right );
          else if( _node -> IsRightChild() ) _node -> m_parent -> SetRightChild( _right );
          else _SetRoot( _right );

          _right -> SetLeftChild( _node );
     }

     void _RotateRight( Node* _node )
     {
          assert( _node );

          Node* _left = _node -> m_left_child;
          _node -> SetLeftChild( _left -> m_right_child );
          if( _node -> IsLeftChild() ) _node -> m_parent -> SetLeftChild( _left );
          else if( _node -> IsRightChild() ) _node -> m_parent -> SetRightChild( _left );
          else _SetRoot( _left );

          _left -> SetRightChild( _node );
     }

     Node* _Delink( Node* _node )
     {
          if( !_node ) return 0;

          while( _node -> m_right_child ) _RotateLeft( _node );

          Node* _left = _node -> m_left_child;

          if( _node -> IsLeftChild() ) _node -> m_parent -> SetLeftChild( _left );
          else if( _node -> IsRightChild() ) _node -> m_parent -> SetRightChild( _left );
          else _SetRoot( _left );

          -- m_count;
          return _node;
     }

     void _Remove( Node* _node )
     {
          if( ( _node = _Delink( _node ) ) ) _Delete( _node );
     }

     Node* _Rename( Node* _node, const K& _new_key )
     {
          if( _node && !ms_cmp.Eq( _node -> m_key, _new_key ) ) 
          {
               _node = _Delink( _node );  
#          if 1
               _node -> m_key = _new_key;
#          else
               _node -> m_key.~K();
               ::new ((void*)&_node -> m_key) K( _new_key );
#          endif

               _node -> m_parent = 0;
               _node -> m_left_child = 0;
               _node -> m_right_child = 0;
               bool _inserted = _Insert1( _node );
               assert( _inserted && "could not insert node" );
               _Insert2( _node );
          }
           
          return _node;
     }

     static Node* _New( const K& _key, const V& _value )
     {
          Node* _node = (Node*) new uint8[sizeof(Node)];
          _node -> m_left_child = 0;
          _node -> m_right_child = 0;
          _node -> m_parent = 0;
          _node -> m_red_color = true;
          ::new ((void*)&_node -> m_key) K( _key );
          ::new ((void*)&_node -> m_value) V( _value );
          return _node;
     }

     static void _Delete( Node* _node )
     {
          assert( _node );
          _node -> m_key.~K();
          _node -> m_value.~V();
          delete [] ((uint8*)_node)
     }

     static void _DeleteTree( Node* _root )
     {
          if( _root )
          {
               _DeleteTree( _root -> m_left_child );
               _DeleteTree( _root -> m_right_child );
               _Delete( _root );
          }
     }

     static void _CopyNode( Node*& _dst, const Node* _src )
     {
          if( _src )
          {
               _dst = _New( _src -> m_key, _src -> m_value );
               _dst -> m_red_color = _src -> m_red_color;
               Node* _left;
               _CopyNode( _left, _src -> m_left_child );
               _dst -> SetLeftChild( _left );
               Node* _right;
               _CopyNode( _left, _src -> m_right_child );
               _dst -> SetRightChild( _right );
          }
          else
          {
               _dst = 0;
          }
     }

     Node* m_root;
     uint m_count;
     static C ms_cmp;
};

template < class K, class V, class C >
C Map< K, V, C >::ms_cmp = C();

template < class K, class V, class C >
void Swap( typename Map< K,V,C >& _a, typename Map< K,V,C >& _b )
{
     _a.Swap( _b );
}

} // namespace ge

#endif//__Map_hpp__
